#include <iostream>
#include <vector>
#include <string>

/**
 * 生成坏字符表以优化字符串匹配过程
 * 该函数根据模式字符串创建一个查找表，用于在字符串匹配算法中快速定位下一个比较位置
 * 主要解决了在字符串匹配中如何高效利用失配信息的问题
 * 
 * @param pattern 待匹配的模式字符串
 * @param size 模式字符串的长度
 * @param badchar 一个长度为256的整型数组，用于存储每个字符最后出现的位置
 */
void badCharHeuristic(const std::string& pattern, int size, int badchar[256]) {
    int i;

    // 初始化坏字符表，将所有字符的最后出现位置设为-1
    for (i = 0; i < 256; i++) {
        badchar[i] = -1;
    }

    // 遍历模式字符串，记录每个字符最后出现的位置
    for (i = 0; i < size; i++) {
        badchar[(int) pattern[i]] = i;
    }
}

/**
 * 使用Boyer-Moore算法在文本中查找模式字符串
 * @param text 要搜索的文本字符串
 * @param pattern 要查找的模式字符串
 * @return 匹配位置的向量，如果未找到则为空
 */
std::vector<int> boyerMooreSearch(const std::string& text, const std::string& pattern) {
    // m和n分别是模式和文本的长度
    int m = pattern.length();
    int n = text.length();

    // 存储匹配位置的向量
    std::vector<int> matches;

    // badchar数组用于存储每个字符在模式中的最后位置
    int badchar[256];
    badCharHeuristic(pattern, m, badchar);

    // s是模式相对于文本的移动量
    int s = 0;
    while (s <= (n - m)) {
        int j = m - 1;

        // 从右向左比较模式和文本中的字符
        while (j >= 0 && pattern[j] == text[s + j]) {
            j--;
        }

        // 如果模式中的所有字符都匹配，则记录匹配位置并移动模式
        if (j < 0) {
            matches.push_back(s);
            s += (s + m < n) ? m - badchar[text[s + m]] : 1;
        } else {
            // 如果字符不匹配，则根据badchar数组移动模式
            s += std::max(1, j - badchar[text[s + j]]);
        }
    }

    // 返回匹配位置的向量
    return matches;
}

int main() {
    std::string text = "ABAAABCD";
    std::string pattern = "ABC";

    std::vector<int> matches = boyerMooreSearch(text, pattern);

    std::cout << "Pattern found at positions: ";
    for (int pos : matches) {
        std::cout << pos << " ";
    }
    std::cout << std::endl;

    return 0;
}